import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class test43 {
    /*给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。



示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1
*/
    public static void main(String[] args) {
        int[] nums = {4,4,3,1,2,1,2,3,10};
        int i = singleNumber2(nums);
        System.out.println(i);
    }
        /*
        方法一：利用set集合去重特性，遇到重复元素就直接删除集合内的元素，最后剩下的就是只出现一次的数字
         */
    public static int singleNumber(int[] nums) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (Integer num : nums) {
            if(!set.add(num)){
                map.remove(num);
            }else {
                map.put(num, set);
            }
        }
       return map.keySet().stream().findFirst().get();
    }
        /*
        方法二：利用异或的特性（不同为1相同为0），相同的数字异或结果为0，且异或满足交换律，因此在循环遍历nums并每次都与0进行异或运算，得到的结果一定是只出现一次的数字
         */
    public static int singleNumber2(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^=num;
        }
        return single;
    }
}
